// LeetCode 144 | 145 | 94
// 前序遍历：根 -> 左 -> 右

// step 1# 定义递归的前序遍历函数
void preOrder(struct TreeNode* root, int* ret, int* returnSize) {
    if (root == NULL)  // 如果当前节点为空，直接返回
        return;

    ret[(*returnSize)++] = root->val;  // 记录当前节点值，并增加结果数组大小

    preOrder(root->left, ret, returnSize);   // 递归遍历左子树
    preOrder(root->right, ret, returnSize);  // 递归遍历右子树
}

// step 2# 前序遍历的主函数，返回遍历结果数组
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret = (int*)malloc(sizeof(int) * 100);  // 分配返回结果数组，最大容量100
    *returnSize = 0;  // 初始化结果大小为0
    preOrder(root, ret, returnSize);  // 调用递归函数进行遍历
    return ret;  // 返回结果数组
}



//中序遍历：
void inOrder(struct TreeNode* node, int* ret, int* returnSize) {
    if(!node)
        return;
    inOrder(node->left, ret, returnSize);
    ret[(*returnSize)++] = node->val;
    inOrder(node->right, ret, returnSize);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret = (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    inOrder(root, ret, returnSize);
    return ret;
}

//后序遍历：
void postOrder(struct TreeNode* node, int* ret, int* returnSize) {
    if(node == NULL) 
        return;
    postOrder(node->left, ret, returnSize);
    postOrder(node->right, ret, returnSize);
    ret[(*returnSize)++] = node->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* ret= (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    postOrder(root, ret, returnSize);
    return ret;
}